import java.util.Arrays;

/**
 * 堆排序（Heap Sort）
 * 堆排序是一种高效的基于比较的排序算法，利用了二叉堆（通常是最大堆）的数据结构特性。它的时间复杂度在最佳、平均和最坏情况下都是稳定的 O(NlogN)。
 * 堆排序主要分为两个阶段：
 * 建堆（Heapify）： 将无序数组构建成一个最大堆（Max-Heap）。
 * 排序（Sort）： 循环地将堆顶元素（最大值）与堆的末尾元素交换，然后对剩余的 N−1 个元素重新调整堆（下沉操作）。
 *
 * @author Liu Yicong
 * @date 2025/9/22
 */
public class HeapSort {
	/**
	 * 对整个数组执行堆排序的入口方法。
	 *
	 * @param arr 待排序的整数数组。
	 */
	public static void sort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}

		int n = arr.length;

		// 1. 建堆阶段：将数组转换成最大堆。
		// 从最后一个非叶子节点开始（索引为 n/2 - 1）向上进行堆化操作。
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i);
		}

		// 2. 排序阶段：依次取出堆顶元素（最大值）。
		// 循环 n-1 次，因为最后剩下的那个元素自然就位。
		for (int i = n - 1; i > 0; i--) {
			// 交换堆顶元素 (arr[0]) 和当前堆的最后一个元素 (arr[i])
			swap(arr, 0, i);

			// 对剩余的 i 个元素重新进行堆化（i 现在的意义是堆的大小）
			heapify(arr, i, 0);
		}
	}

	/**
	 * 堆化操作（Heapify）：确保以 i 为根节点的子树满足最大堆的性质。
	 * 也称为“下沉”操作。
	 * * @param arr 数组。
	 *
	 * @param heapSize 当前堆的有效大小。
	 * @param i        需要进行堆化的子树的根节点索引。
	 */
	private static void heapify(int[] arr, int heapSize, int i) {
		int largest = i;          // 假设当前节点是最大值
		int left = 2 * i + 1;     // 左子节点索引
		int right = 2 * i + 2;    // 右子节点索引

		// 如果左子节点存在且大于当前最大值
		if (left < heapSize && arr[left] > arr[largest]) {
			largest = left;
		}

		// 如果右子节点存在且大于当前最大值
		if (right < heapSize && arr[right] > arr[largest]) {
			largest = right;
		}

		// 如果最大值不是根节点 i，则进行交换
		if (largest != i) {
			swap(arr, i, largest);

			// 递归地对被交换的子树进行堆化，确保其仍然满足最大堆性质
			heapify(arr, heapSize, largest);
		}
	}

	/**
	 * 辅助方法：交换数组中两个索引位置的元素。
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// --- 测试代码 ---
	public static void main(String[] args) {
		int[] data = {12, 11, 13, 5, 6, 7};
		System.out.println("原始数组: " + Arrays.toString(data));

		HeapSort.sort(data);

		System.out.println("排序结果: " + Arrays.toString(data));

		int[] data2 = {5, 4, 3, 2, 1};
		HeapSort.sort(data2);
		System.out.println("反序数组排序结果: " + Arrays.toString(data2));

		int[] data3 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
		HeapSort.sort(data3);
		System.out.println("有序数组排序结果: " + Arrays.toString(data3));
	}
}
